package site.wanjiahao;

public class Knapsack {

    public static void main(String[] args) {
        int[] weights = {2, 2, 6, 5, 4};
        int[] values = {6, 3, 5, 4, 6};
        // 背包最大承重为10
        int capacity = 10;
        System.out.println(knapsack3(weights, values, capacity));
    }

    // 背包恰好装满的最大价值
    static int knapsack(int[] weights, int[] values, int capacity) {
        // 定义dp[i][j]，承重前i件物品，背包重量为j的最大价值
        if (weights == null ||
                values == null ||
                values.length == 0 ||
                weights.length != values.length ||
                capacity == 0) return 0;
        // 使用一维数组优化，只用到了上面一个，但是需要从后往前遍历。数据才能正确
        int[] dp = new int[capacity + 1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MIN_VALUE;
        }
        for (int i = 1; i <= weights.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                // 选择，与不选择的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
            }
        }
        return dp[capacity] < 0? -1: dp[capacity];
    }

    static int knapsack3(int[] weights, int[] values, int capacity) {
        // 定义dp[i][j]，承重前i件物品，背包重量为j的最大价值
        if (weights == null ||
                values == null ||
                values.length == 0 ||
                weights.length != values.length ||
                capacity == 0) return 0;
        // 使用一维数组优化，只用到了上面一个，但是需要从后往前遍历。数据才能正确
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= weights.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                // 选择，与不选择的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
            }
        }
        return dp[capacity];
    }

    static int knapsack2(int[] weights, int[] values, int capacity) {
        // 定义dp[i][j]，承重前i件物品，背包重量为j的最大价值
        if (weights == null ||
                values == null ||
                values.length == 0 ||
                weights.length != values.length ||
                capacity == 0) return 0;
        // 使用一维数组优化，只用到了上面一个，但是需要从后往前遍历。数据才能正确
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= weights.length; i++) {
            for (int j = capacity; j >= 1; j--) {
                if (j >= weights[i - 1]) {
                    // 选择，与不选择的最大价值
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[capacity];
    }

    static int knapsack1(int[] weights, int[] values, int capacity) {
        // 定义dp[i][j]，承重前i件物品，背包重量为j的最大价值
        if (weights == null ||
                values == null ||
                values.length == 0 ||
                weights.length != values.length ||
                capacity == 0) return 0;
        int[][] dp = new int[weights.length + 1][capacity + 1];
        for (int j = 1; j <= capacity; j++) {
            for (int i = 1; i <= weights.length; i++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择，与不选择的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[weights.length][capacity];
    }


}
